 /**
  ********************************************
  Linked List Class
  ********************************************
  
 * This program uses "LinkedList" in conjucation with "node" to complete Homework 3
 * 
 * This class comes with a "removeFront" method
 * 
 * @author (Greg Shevach & Chris Nerf) 
 * @version (v1.01)
 * @revision added error throwing for better error handling in .front() and .removeFront(), otherwise undefined behavior on empty list
 * @revision added fix with .removeFront() which caused nullpointerException error to be thrown
 * @date (9/27/11)
 */
         
public class LinkedList<T> {
            
    private Node<T> head;
    private Node<T> tail;
    private int size;

    public LinkedList() {
    head = null;
    tail = null;
    size = 0;
    }

    public void addRear( T element ) 
    {
    	Node<T> temp = new Node<T>( element );

    	if( isEmpty() )
    		head = temp;
    	else
    		tail.setnextLeft( temp );

    	tail = temp;
    	++size;
    }
 

    public T front() throws java.lang.RuntimeException //added error throwing, instead of just a string error message
    {
    T result = null;
    if( isEmpty() ) //@Greg the way it was would, printing a string if it is empty then continuing return result would cause undefined behavior.
        throw new java.lang.RuntimeException("The Linked List is empty");
    else
        result = head.getElement();
    return ( result );
    }
    
    //added this to get the first node of the list
    public Node getFrontNode() throws java.lang.RuntimeException //added error throwing, instead of just a string error message
    {
    Node result = null;
    if( isEmpty() ) //@Greg the way it was would, printing a string if it is empty then continuing return result would cause undefined behavior.
        throw new java.lang.RuntimeException("The Linked List is empty");
    else
        result = head;
    return ( result );
    }
    
    public Node getHeadNode()
    {
    	return head;
    }

    public boolean isEmpty() {
    return ( size == 0 );
    }

    public int size() {
    return ( size );
    }

    public String toString() {
    String s = new String();
    Node<T> mover = head;
    while( mover != null ) {
        s += ( (mover.getElement()).toString() + " " );
        mover = mover.getnextLeft();
    }
    return ( s );
    }
    
    public T removeFront() throws java.lang.RuntimeException //added error throwing, instead of just a string error message
    {  //Removes the first element of the linked list
    		if(isEmpty())//If list is empty, system message
    		      throw new java.lang.RuntimeException("The Linked List is empty"); //@Greg the way it was would, printing a string if it is empty then continuing return result would cause undefined behavior.
    		   
    Node<T> tempHead = this.head.getnextLeft(); //get the location of the next element
   T result = this.front(); // this is the value of the first element
    this.head.remove(this.front());  //Removes the first element
    this.head= tempHead;                   //sets the head to the next element
   
    
   
    
    return ( result );      //Returns what was removed
    
  }
    
    //for debugging
    public void print()
    {
    	Node<T> mover = head;
    	while (mover != null)
    	{
    		mover.printValue();
    		mover  = mover.getnextLeft();
    		System.out.println();
    	}
    	
    }
    

    
    public void sortList()
    {
    	boolean sorted = false;
    	
    	while(!sorted)
    	{
    		sorted = true;
    		for(Node mover = head; mover.getnextLeft() != null; mover = mover.getnextLeft())
    		{
    			//sorting by frequency
    			try{
    			if(mover.getCount() < mover.getnextLeft().getCount()) //check to see which has the less value, the current or the next
    			{
    				//iff the current node has a lesser value, let's take a look at it
    				int lesser = (Integer)mover.getElement();  //get the value of the element, as an integer
    				int lesserCount = mover.getCount(); //get the number of elements
    				
    				mover.setElement(mover.getnextLeft().getElement()); //set the value of the next node to the value of this node
    				mover.setCount(mover.getnextLeft().getCount()); //set the count of the next node to this node
    				
    				mover.getnextLeft().setElement(lesser); //set the next node's value to the value stored in lesser
    				mover.getnextLeft().setCount(lesserCount); //set the count in the next node to the count stored in lesser
    				
    				sorted = false; //set sorted to false so we can do all this over again
    				
    			}}catch (Exception wtf)
    			{}
    		}
    	}
    }
  
}